package algorithm;

public class Sum {
    static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            valAddToSb(sb1,l1);
            valAddToSb(sb2,l2);
            ListNode end;
            if (sb1.length() >= sb2.length()) {
                end = sumToListNode(sb1, sb2);
            } else {
                end = sumToListNode(sb2, sb1);
            }
            return end;
        }

        private ListNode sumToListNode(StringBuilder sb1,StringBuilder sb2) {
            int sb1Length=sb1.length();
            int sb2Length=sb2.length();
            int a = Integer.valueOf(sb1.substring(sb1Length - 1, sb1Length)) + Integer.valueOf(sb2.substring(sb2Length - 1, sb2Length));
            boolean isCarry = false;
            if (a > 9) {
                a -= 10;
                isCarry = true;
            }
            ListNode retNode = new ListNode(a);
            ListNode tempNode = retNode;
            for (int i = 1; i < sb1Length; i++) {
                int b;
                if (i >= sb2Length) {
                    b = Integer.valueOf(sb1.substring(sb1Length - i - 1, sb1Length - i));
                } else {
                    b = Integer.valueOf(sb1.substring(sb1Length - i - 1, sb1Length - i)) + Integer.valueOf(sb2.substring(sb2Length - i - 1, sb2Length - i));
                }
                if (isCarry) {
                    b++;
                }
                if (b > 9) {
                    b -= 10;
                    isCarry = true;
                } else {
                    isCarry = false;
                }
                ListNode node = new ListNode(b);
                tempNode.next = node;
                tempNode = node;
            }
            if (isCarry) {
                ListNode node = new ListNode(1);
                tempNode.next = node;
                tempNode = node;
            }
            return retNode;
        }

        private void valAddToSb(StringBuilder sb,ListNode listNode) {
            if (listNode.next != null) {
                valAddToSb(sb, listNode.next);
            }
            sb.append(listNode.val);
            return;
        }

        public static void main(String[] args) {
            ListNode l1 = new ListNode(5);
            ListNode l2 = new ListNode(5);
            Solution s = new Solution();
            s.addTwoNumbers(l1, l2);
        }

        public static class ListNode {
            int val;

            ListNode next;

            ListNode(int x) {
                val = x;
            }
        }
    }
}
